Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie nieposortowanej tablicy?

Jesteś ofiarą niepowodzenia przewidywania gałęzi.
Co to jest przewidywanie gałęzi?
Rozważ węzeł kolejowy:
Zdjęcie: Mecanismo, za pośrednictwem Wikimedia Commons. Używany na licencji CC-By-SA 3.0.
Teraz, dla celów argumentacji, przypuśćmy, że dzieje się to w XIX wieku - przed długodystansową komunikacją radiową.
Jesteś operatorem skrzyżowania i słyszysz nadjeżdżający pociąg. Nie masz pojęcia, w którą stronę ma iść. Zatrzymujesz pociąg, aby zapytać maszynistę, w którym kierunku chcą. Następnie odpowiednio ustawiasz przełącznik.
Pociągi są ciężkie i mają dużą bezwładność. Dlatego uruchamianie i zwalnianie zajmuje im wieki.
Czy jest lepszy sposób? Zgadujesz, w którym kierunku pojedzie pociąg!
Jeśli dobrze zgadłeś, to trwa dalej.
Jeśli źle zgadłeś, kapitan zatrzyma się, cofnie i wrzeszczy na ciebie, żebyś puścił przełącznik. Następnie może ponownie uruchomić inną ścieżkę.
Jeśli za każdym razem zgadniesz, pociąg nigdy nie będzie musiał się zatrzymywać. Jeśli zbyt często źle zgadujesz, pociąg będzie spędzał dużo czasu na zatrzymywaniu, wykonywaniu kopii zapasowych i ponownym uruchomieniu.
Rozważmy instrukcję if: na poziomie procesora jest to instrukcja rozgałęzienia:
Jesteś przetwórcą i widzisz oddział. Nie masz pojęcia, w którą stronę to pójdzie. Co robisz? Zatrzymujesz wykonywanie i czekasz, aż poprzednie instrukcje zostaną zakończone. Następnie podążasz właściwą ścieżką.
Nowoczesne procesory są skomplikowane i mają długie rurociągi. Dlatego „rozgrzewka” i „zwolnienie” zajmuje im wieki.
Czy jest lepszy sposób? Zgadujesz, w którym kierunku pójdzie gałąź!
Jeśli dobrze zgadłeś, kontynuujesz wykonywanie.
Jeśli źle zgadłeś, musisz przepłukać rurociąg i wrócić do gałęzi. Następnie możesz ponownie uruchomić inną ścieżkę.
Jeśli za każdym razem zgadniesz, wykonanie nigdy nie będzie musiało się kończyć. Jeśli zbyt często błędnie odgadujesz, spędzasz dużo czasu na zwłokach, wycofywaniu i ponownym uruchamianiu.
To jest przewidywanie gałęzi. Przyznaję, że nie jest to najlepsza analogia, skoro pociąg mógłby po prostu sygnalizować kierunek flagą. Ale w komputerach procesor do ostatniej chwili nie wie, w którym kierunku pójdzie gałąź.
Jak więc odgadnąć strategicznie, aby zminimalizować liczbę razy, kiedy pociąg musi się cofnąć i zjechać inną ścieżką? Patrzysz na przeszłą historię! Jeśli pociąg wyjeżdża w 99% przypadków, to chyba w lewo. Jeśli się zmienia, to zmieniasz domysły. Jeśli co trzy razy idzie w jedną stronę, zgadujesz to samo ...
Innymi słowy, próbujesz zidentyfikować wzorzec i podążać za nim. Mniej więcej tak działają predyktory gałęzi.
Większość aplikacji ma dobrze działające gałęzie. Tak więc nowoczesne predyktory branżowe zazwyczaj osiągają współczynnik trafień> 90%. Ale w obliczu nieprzewidywalnych gałęzi bez rozpoznawalnych wzorców predykatory gałęzi są praktycznie bezużyteczne.
Dalsza lektura: artykuł „Przewidywanie gałęzi” w Wikipedii.
Jak wskazano powyżej, winowajcą jest ta instrukcja if:
if (dane [c]> = 128)
suma + = dane [c];
Zwróć uwagę, że dane są równomiernie rozłożone między 0 a 255. Gdy dane są posortowane, w przybliżeniu pierwsza połowa iteracji nie spowoduje wprowadzenia instrukcji if. Następnie wszyscy wejdą w instrukcję if.
Jest to bardzo przyjazne dla predyktora gałęzi, ponieważ gałąź kolejno porusza się w tym samym kierunku wiele razy. Nawet prosty licznik nasycenia prawidłowo przewidział gałąź, z wyjątkiem kilku iteracji po zmianie kierunku.
Szybka wizualizacja:
T = zajęta gałąź
N = gałąź nie zajęta
dane [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
gałąź = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTT ... TTTTTTTTTT (łatwe do przewidzenia)
Jednak gdy dane są całkowicie losowe, predyktor rozgałęzienia staje się bezużyteczny, ponieważ nie może przewidywać losowych danych. Zatem prawdopodobnie będzie około 50% błędnych przewidywań (nie lepiej niż przypadkowe zgadywanie).
data [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
gałąź = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (całkowicie losowe - trudne do przewidzenia)
Więc co można zrobić?
Jeśli kompilator nie jest w stanie zoptymalizować gałęzi do ruchu warunkowego, możesz spróbować kilku hacków, jeśli chcesz poświęcić czytelność na rzecz wydajności.
Zastąpić:
if (dane [c]> = 128)
suma + = dane [c];
z:
int t = (dane [c] - 128) >> 31;
suma + = ~ t & data [c];
Eliminuje to gałąź i zastępuje ją niektórymi operacjami bitowymi.
(Zwróć uwagę, że ten hack nie jest ściśle równoważny z oryginalną instrukcją if. Ale w tym przypadku obowiązuje dla wszystkich wejściowych wartości danych []).
Benchmarki: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - wersja x64
// Oddział - losowo
sekundy = 11,777
// Oddział - posortowane
sekundy = 2,352
// Bezgałęziowe - losowe
sekundy = 2,564
// Bezgałęziowe - posortowane
sekundy = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Oddział - losowo
sekundy = 10,93293813
// Oddział - posortowane
sekundy = 5,643797077
// Bezgałęziowe -Losowy
sekundy = 3,113581453
// Bezgałęziowe - posortowane
sekundy = 3,186068823
Obserwacje:
Dzięki gałęzi: istnieje ogromna różnica między danymi posortowanymi i nieposortowanymi.
Z hackiem: nie ma różnicy między danymi posortowanymi i nieposortowanymi.
W przypadku C ++ hack jest właściwie odrobinę wolniejszy niż w przypadku gałęzi, gdy dane są sortowane.
Ogólną zasadą jest unikanie rozgałęzień zależnych od danych w krytycznych pętlach (tak jak w tym przykładzie).
Aktualizacja:
GCC 4.6.1 z -O3 lub -ftree-vectorize na x64 jest w stanie wygenerować ruch warunkowy. Nie ma więc różnicy między danymi posortowanymi i nieposortowanymi - oba są szybkie.
(Lub trochę szybko: dla już posortowanego przypadku cmov może być wolniejsze, zwłaszcza jeśli GCC umieści go na ścieżce krytycznej zamiast po prostu dodać, szczególnie na Intelu przed Broadwellem, gdzie cmov ma opóźnienie 2 cykli: flaga optymalizacji gcc -O3 spowalnia kod niż -O2)
VC ++ 2010 nie jest w stanie wygenerować ruchów warunkowych dla tej gałęzi nawet pod / Ox.
Kompilator Intel C ++ (ICC) 11 robi coś cudownego. Zamienia dwie pętle, podnosząc w ten sposób nieprzewidywalną gałąź do pętli zewnętrznej. Jest więc nie tylko odporny na błędne przewidywania, ale jest również dwukrotnie szybszy niż wszystko, co może wygenerować VC ++ i GCC! Innymi słowy, ICC wykorzystało pętlę testową, aby pokonać benchmark ...
Jeśli podasz kompilatorowi Intela kod bezgałęziowy, to po prostu wektoryzuje go w prawo ... i jest tak samo szybki jak w przypadku gałęzi (z wymianą pętli).
To pokazuje, że nawet dojrzałe, nowoczesne kompilatory mogą znacznie różnić się pod względem możliwości optymalizacji kodu ...
|
Przewidywanie gałęzi.
W przypadku posortowanej tablicy dane warunku [c]> = 128 są najpierw fałszywe dla ciągu wartości, a następnie stają się prawdziwe dla wszystkich późniejszych wartości. Łatwo to przewidzieć. W przypadku tablicy niesortowanej płacisz za koszt rozgałęzienia.
|
Powodem, dla którego wydajność drastycznie się poprawia, gdy dane są sortowane, jest to, że kara za przewidywanie gałęzi została usunięta, co pięknie wyjaśniono w odpowiedzi Mysticial.
Teraz, jeśli spojrzymy na kod
if (dane [c]> = 128)
suma + = dane [c];
możemy stwierdzić, że znaczenie tej konkretnej gałęzi if ... else ... polega na dodaniu czegoś, gdy warunek jest spełniony. Ten typ gałęzi można łatwo przekształcić w warunkową instrukcję ruchu, która byłaby skompilowana w warunkową instrukcję ruchu: cmovl w systemie x86. Gałąź, a tym samym potencjalna kara za prognozowanie gałęzi, jest usuwana.
W C, a więc w C ++, instrukcja, która mogłaby zostać skompilowana bezpośrednio (bez żadnej optymalizacji) do instrukcji warunkowego ruchu w x86, jest operatorem trójskładnikowym ...? ...: .... Więc przepisujemy powyższe stwierdzenie na równoważne:
suma + = dane [c]> = 128? data [c]: 0;
Zachowując czytelność, możemy sprawdzić współczynnik przyspieszenia.
Na Intel Core i7-2600K @ 3,4 GHz i Visual Studio 2010 Release Mode, test porównawczy to (format skopiowany z Mysticial):
x86
// Oddział - losowo
sekundy = 8,885
// Oddział - posortowane
sekundy = 1,528
// Bezgałęziowe - losowe
sekundy = 3,716
// Bezgałęziowe - posortowane
sekundy = 3,71
x64
// Oddział - losowo
sekundy = 11,302
// Oddział - posortowane
sekundy = 1,830
// Bezgałęziowe - losowe
sekundy = 2,736
// Bezgałęziowe - posortowane
sekundy = 2,737
Wynik jest solidny w wielu testach. Osiągamy duże przyspieszenie, gdy wynik gałęzi jest nieprzewidywalny, ale trochę cierpimy, gdy jest przewidywalny. W rzeczywistości podczas korzystania z ruchu warunkowego wydajność jest taka sama, niezależnie od wzorca danych.
Przyjrzyjmy się teraz bliżej, badając zestaw x86, który generują. Dla uproszczenia używamy dwóch funkcji max1 i max2.
max1 używa gałęzi warunkowej, jeśli ... else ...:
int max1 (int a, int b) {
jeśli (a> b)
return a;
jeszcze
powrót b;
}
max2 używa operatora trójskładnikowego ...? ...: ...:
int max2 (int a, int b) {
return a> b? a: b;
}
Na maszynie x86-64 GCC -S generuje zestaw poniżej.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
wyjechać
gnić
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
wyjechać
gnić
max2 używa znacznie mniej kodu dzięki zastosowaniu instrukcji cmovge. Ale prawdziwym zyskiem jest to, że max2 nie obejmuje skoków gałęzi, jmp, co spowodowałoby znaczny spadek wydajności, gdyby przewidywany wynik był nieprawidłowy.
Dlaczego więc ruch warunkowy działa lepiej?
W typowym procesorze x86 wykonanie instrukcji jest podzielone na kilka etapów. Z grubsza mamy różny sprzęt do radzenia sobie na różnych etapach. Nie musimy więc czekać na zakończenie jednej instrukcji, aby rozpocząć nową. Nazywa się to rurociągami.
W przypadku rozgałęzienia następna instrukcja jest określona przez poprzednią, więc nie możemy wykonać potokowania. Musimy albo czekać, albo przewidywać.
W przypadku ruchu warunkowegowykonanie instrukcji ruchu warunkowego jest podzielone na kilka etapów, ale wcześniejsze etapy, takie jak pobieranie i dekodowanie, nie zależą od wyniku poprzedniej instrukcji; tylko ostatnie etapy wymagają wyniku. W ten sposób czekamy ułamek czasu wykonania jednej instrukcji. Dlatego wersja warunkowego przeniesienia jest wolniejsza niż gałąź, gdy przewidywanie jest łatwe.
Książka Computer Systems: A Programmer's Perspective, drugie wydanie, wyjaśnia to szczegółowo. Możesz sprawdzić sekcję 3.6.6 dotyczącą instrukcji warunkowego przeniesienia, cały rozdział 4 dotyczący architektury procesora oraz sekcję 5.11.2, aby zapoznać się ze specjalnym traktowaniem przewidywania rozgałęzień i kar za niedopuszczenie.
Czasami niektóre nowoczesne kompilatory mogą zoptymalizować nasz kod do asemblacji z lepszą wydajnością, czasami niektóre kompilatory nie mogą (dany kod używa natywnego kompilatora programu Visual Studio). Znajomość różnicy wydajności między gałęzią a ruchem warunkowym, gdy jest nieprzewidywalny, może pomóc nam napisać kod z lepszą wydajnością, gdy scenariusz staje się tak złożony, że kompilator nie może ich automatycznie zoptymalizować.
|
Jeśli interesuje Cię jeszcze więcej optymalizacji, które można wykonać w tym kodzie, rozważ to:
Zaczynając od oryginalnej pętli:
for (unsigned i = 0; i <100000; ++ i)
{
for (unsigned j = 0; j  = 128)
suma + = dane [j];
}
}
Dzięki wymianie pętli możemy bezpiecznie zmienić tę pętlę na:
for (unsigned j = 0; j  = 128)
suma + = dane [j];
}
}
Następnie możesz zobaczyć, że warunek if jest stały podczas wykonywania pętli i, więc możesz wyciągnąć if out:
for (unsigned j = 0; j  = 128)
{
for (unsigned i = 0; i <100000; ++ i)
{
suma + = dane [j];
}
}
}
Następnie widzisz, że pętla wewnętrzna może zostać zwinięta w jedno wyrażenie, zakładając, że model zmiennoprzecinkowy na to pozwala (na przykład / fp: fast jest rzucane)
for (unsigned j = 0; j  = 128)
{
suma + = dane [j] * 100000;
}
}
Ten jest 100 000 razy szybszy niż wcześniej.
|
Bez wątpienia niektórzy z nas byliby zainteresowani sposobami identyfikacji kodu, który jest problematyczny dla predyktora gałęzi procesora. Narzędzie Valgrind cachegrind ma symulator predykatora gałęzi, włączany za pomocą flagi --branch-sim = yes. Prześledzenie przykładów w tym pytaniu, z liczbą zewnętrznych pętli zredukowanych do 10000 i skompilowanych za pomocą g ++, daje następujące wyniki:
Posortowane:
== 32551 == Oddziały: 656,645,130 (656,609,208 warunku + 35,922 ind)
== 32551 == Mispredicts: 169.556 (169.095 kond. + 461 ind.)
== 32551 == Mispred rate: 0,0% (0,0% + 1,2%)
Nieposortowany:
== 32555 == Oddziały: 655 996 082 (655 960 160 warunku + 35 922 ind)
== 32555 == Mispredicts: 164.073.152 (164.072.692 cond + 460 ind)
== 32555 == Mispred rate: 25,0% (25,0% + 1,2%)
Drążąc w dół do wyjścia wiersz po wierszu generowanego przez cg_annotate, widzimy dla omawianej pętli:
Posortowane:
Bc Bcm Bi Bim
10,001 4 0 0 dla (bez znaku i = 0; i <10000; ++ i)
. . . . {
. . . . // pętla główna
327 690 000 10 016 0 0 for (unsigned c = 0; c  = 128)
0 0 0 0 suma + = dane [c];
. . . . }
. . . . }
Nieposortowany:
Bc Bcm Bi Bim
10,001 4 0 0 dla (bez znaku i = 0; i <10000; ++ i)
. . . . {
. . . . // pętla główna
327 690 000 10 038 0 0 for (unsigned c = 0; c  = 128)
0 0 0 0 suma + = dane [c];
. . . . }
. . . . }
Pozwala to łatwo zidentyfikować problematyczną linię - w nieposortowanej wersji linia if (dane [c]> = 128) powoduje 164 050 007 błędnie przewidzianych gałęzi warunkowych (Bcm) w modelu predykatora gałęzi cachegrind, podczas gdy powoduje tylko 1006 w wersji posortowanej .
Alternatywnie w systemie Linux można użyć podsystemu liczników wydajności do wykonania tego samego zadania, ale z natywną wydajnością przy użyciu liczników procesora.
perf stat ./sumtest_sorted
Posortowane:
Statystyki licznika wydajności dla „./sumtest_sorted”:
11808.095776 task-clock # 0.998 Wykorzystane procesory
1062 przełączników kontekstowych # 0,090 K / s
14 migracji procesora # 0,001 K / sek
337 błędów stronicowania # 0,029 K / sek
26 487 882 764 cykli 2,243 GHz
41,025,654,322 instrukcje # 1,55 insns na cykl
6.558.871.379 oddziałów # 555.455 M / sek
567,204 pominięcia gałęzi # 0,01% wszystkich gałęzi
Upłynęło 11,827228330 sekund
Nieposortowany:
Występstatystyki licznika dla „./sumtest_unsorted”:
28877.954344 task-clock # 0.998 Wykorzystane procesory
2584 przełączniki kontekstowe # 0,089 K / s
18 migracji procesora # 0,001 K / s
335 błędów stronicowania # 0,012 K / sek
65 076 127 595 cykli # 2,253 GHz
41 032 528 741 instrukcji # 0,63 insns na cykl
6.560.579.013 oddziałów # 227,183 M / sek
1,646,394,749 brakujących gałęzi # 25,10% wszystkich oddziałów
Upłynęło 28,935500947 sekund
Może również wykonywać adnotacje kodu źródłowego z dezasemblacją.
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Procent | Kod źródłowy i demontaż sumtest_unsorted
------------------------------------------------
...
: suma + = dane [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39,97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: dodaj% rax, -0x30 (% rbp)
...
Więcej informacji można znaleźć w samouczku dotyczącym wydajności.
|
Właśnie przeczytałem to pytanie i odpowiedzi na nie, i czuję, że brakuje odpowiedzi.
Powszechnym sposobem na wyeliminowanie przewidywania gałęzi, które sprawdzają się szczególnie dobrze w językach zarządzanych, jest przeszukiwanie tabeli zamiast używania gałęzi (chociaż nie testowałem tego w tym przypadku).
To podejście działa ogólnie, jeśli:
jest to mały stół i prawdopodobnie będzie przechowywany w pamięci podręcznej procesora, oraz
uruchamiasz rzeczy w dość ciasnej pętli i / lub procesor może wstępnie załadować dane.
Tło i dlaczego
Z punktu widzenia procesora twoja pamięć jest wolna. Aby zrekompensować różnicę w szybkości, w procesor wbudowano kilka pamięci podręcznych (pamięć podręczna L1 / L2). Wyobraź sobie, że wykonujesz ładne obliczenia i stwierdzisz, że potrzebujesz kawałka pamięci. Procesor wykona operację „ładowania” i załaduje część pamięci do pamięci podręcznej - a następnie użyje pamięci podręcznej do wykonania pozostałych obliczeń. Ponieważ pamięć jest stosunkowo wolna, to „ładowanie” spowolni twój program.
Podobnie jak przewidywanie rozgałęzień, zostało to zoptymalizowane w procesorach Pentium: procesor przewiduje, że musi załadować część danych i próbuje załadować je do pamięci podręcznej, zanim operacja faktycznie trafi do pamięci podręcznej. Jak już widzieliśmy, przewidywanie gałęzi czasami idzie strasznie źle - w najgorszym przypadku trzeba cofnąć się i faktycznie poczekać na obciążenie pamięci, co zajmie wieczność (innymi słowy: niepowodzenie przewidywania gałęzi jest złe obciążenie po niepowodzeniu przewidywania gałęzi jest po prostu okropne!).
Na szczęście dla nas, jeśli wzorzec dostępu do pamięci jest przewidywalny, procesor załaduje go do swojej szybkiej pamięci podręcznej i wszystko jest w porządku.
Pierwszą rzeczą, którą musimy wiedzieć, jest to, co jest małe? Chociaż mniejsze jest generalnie lepsze, ogólną zasadą jest trzymanie się tabel przeglądowych o rozmiarze <= 4096 bajtów. Jako górny limit: jeśli twoja tabela przeglądowa jest większa niż 64 KB, prawdopodobnie warto to ponownie rozważyć.
Konstruowanie stołu
Więc ustaliliśmy, że możemy stworzyć mały stół. Następną rzeczą do zrobienia jest wprowadzenie funkcji wyszukiwania. Funkcje wyszukiwania są zwykle małymi funkcjami, które używają kilku podstawowych operacji na liczbach całkowitych (i, or, xor, shift, add, remove, a być może mnożenie). Chcesz, aby Twoje dane wejściowe zostały przetłumaczone za pomocą funkcji wyszukiwania na pewien rodzaj „unikalnego klucza” w tabeli, który następnie po prostu daje odpowiedź na całą pracę, którą chciałeś wykonać.
W tym przypadku:> = 128 oznacza, że ​​możemy zachować wartość, <128 oznacza, że ​​się go pozbywamy. Najłatwiej to zrobić, używając „AND”: jeśli go zachowamy, ORAZ to za pomocą 7FFFFFFF; jeśli chcemy się go pozbyć, to ORAZ to z 0. Zauważ też, że 128 to potęga 2 - możemy więc zrobić tablicę zawierającą 32768/128 liczb całkowitych i wypełnić ją jednym zerem i dużą ilością 7FFFFFFFF.
Zarządzane języki
Możesz się zastanawiać, dlaczego to działa dobrze w zarządzanych językach. W końcu języki zarządzane sprawdzają granice tablic za pomocą gałęzi, aby upewnić się, że nie zepsujesz ...
Cóż, nie do końca ... :-)
Było sporo pracy nad wyeliminowaniem tej gałęzi dla języków zarządzanych. Na przykład:
for (int i = 0; i  = 128)? c: 0;
}
// Test
DateTime startTime = System.DateTime.Now;
długa suma = 0;
dla (int i = 0; i <100000; ++ i)
{
// Pętla główna
for (int j = 0; j  ());
for (unsigned c = 0; c  = 128
sum = sum + data1 (j);
koniec
koniec
koniec
toc;
ExeTimeWithSorting = toc - tic;
Wyniki dla powyższego kodu MATLAB są następujące:
a: Upływający czas (bez sortowania) = 3479,880861 sekund.
b: Upływający czas (z sortowaniem) = 2377,873098 sekund.
Wyniki kodu C jak w @GManNickG otrzymuję:
a: Upływający czas (bez sortowania) = 19,8761 sek.
b: Upływający czas (z sortowaniem) = 7,37778 sek.
Na tej podstawie wygląda na to, że MATLAB jest prawie 175 razy wolniejszy niż implementacja C bez sortowania i 350 razy wolniejszy z sortowaniem. Innymi słowy, efekt (predykcji rozgałęzienia) wynosi 1,46x dla implementacji MATLAB i 2,7x dla implementacji C.
|
Założenie przy innych odpowiedziach, że należy posortować dane, nie jest poprawne.
Poniższy kod nie sortuje całej tablicy, ale tylko 200-elementowe segmenty, dzięki czemu działa najszybciej.
Sortowanie tylko sekcji k-elementów kończy przetwarzanie wstępne w czasie liniowym O (n), a nie w czasie O (n.log (n)) potrzebnym do posortowania całej tablicy.
#include 
#include 
#include 
int main () {
dane int [32768]; const int l = rozmiar danych / rozmiar danych [0];
for (unsigned c = 0; c  = 128)
suma + = dane [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
To również „udowadnia”, że nie ma to nic wspólnego z żadnym problemem algorytmicznym, takim jak porządek sortowania, i rzeczywiście jest to przewidywanie rozgałęzień.
|
Odpowiedź Bjarne Stroustrupa na to pytanie:
To brzmi jak pytanie do wywiadu. Czy to prawda? Skąd miałbyś wiedzieć? Nie jest dobrym pomysłem odpowiadanie na pytania dotyczące wydajności bez wcześniejszego wykonywania pewnych pomiarów, dlatego ważne jest, aby wiedzieć, jak dokonywać pomiarów.
Więc spróbowałem z wektorem miliona liczb całkowitych i otrzymałem:
Posortowano już 32995 milisekund
Przetasowane 125944 milisekund
Już posortowano 18610 milisekund
Przetasowano 133304 milisekund
Posortowano już 17942 milisekund
Przetasowane 107858 milisekund
Biegałem to kilka razy, żeby się upewnić. Tak, to zjawisko jest prawdziwe. Mój kod klucza to:
void run (vector  & v, const string & label)
{
auto t0 = system_clock :: now ();
sort (v.begin (), v.end ());
auto t1 = system_clock :: now ();
cout << label
<< duration_cast  (t1 - t0) .count ()
<< "milisekundy \ n";
}
void tst ()
{
wektor  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "już posortowane");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "shuffled");
}
Przynajmniej to zjawisko jest prawdziwe w przypadku tego kompilatora, biblioteki standardowej i ustawień optymalizatora. Różne implementacje mogą i dają różne odpowiedzi. W rzeczywistości ktoś przeprowadził bardziej systematyczne badanie (szybkie wyszukiwanie w Internecie go znajdzie) i większość wdrożeń wykazuje ten efekt.
Jednym z powodów jest przewidywanie rozgałęzień: kluczowa operacja w algorytmie sortowania to „if (v [i]  = 128. Oznacza to, że możemy łatwo wyodrębnić pojedynczy bit, który powie nam, czy chcemy wartość, czy nie: przesuwając dane po prawej stronie 7 bitów, zostaje nam 0 bitów lub 1 bit i chcemy dodać wartość tylko wtedy, gdy mamy 1 bit. Nazwijmy to „bitem decyzyjnym”.
Używając wartości 0/1 bitu decyzyjnego jako indeksu tablicy, możemy stworzyć kod, który będzie równie szybki, niezależnie od tego, czy dane są posortowane, czy nie. Nasz kod zawsze doda wartość, ale gdy bit decyzji będzie równy 0, dodamy wartość gdzieś, na czym nam nie zależy. Oto kod:
// Test
clock_t start = clock ();
długi długi a [] = {0, 0};
długa suma;
for (unsigned i = 0; i <100000; ++ i)
{
// Pętla główna
for (unsigned c = 0; c > 7);
a [j] + = dane [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
suma = a [1];
Ten kod marnuje połowę dodatków, ale nigdy nie powoduje błędu przewidywania gałęzi. W przypadku danych losowych jest znacznie szybszy niż wersja z rzeczywistą instrukcją if.
Ale w moich testach jawna tabela przeglądowa była nieco szybsza niż ta, prawdopodobnie dlatego, że indeksowanie do tabeli przeglądowej było nieco szybsze niż przesunięcie bitowe. To pokazuje, jak mój kod konfiguruje i używa tabeli odnośników (bez wyobraźni nazwanej lut dla „LookUp Table” w kodzie). Oto kod w C ++:
// Zadeklaruj, a następnie wypełnij tabelę przeglądową
int lut [256];
for (unsigned c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Użyj tabeli przeglądowej po jej zbudowaniu
for (unsigned i = 0; i <100000; ++ i)
{
// Pętla główna
for (unsigned c = 0; c )
węzeł = węzeł-> pLeft;
jeszcze
węzeł = węzeł-> pRight;
ta biblioteka zrobiłaby coś takiego:
i = (x  wartość);
węzeł = węzeł-> łącze [i];
To fajne rozwiązanie i może się uda.
|
Bardzo aktywne pytanie. Zdobądź 10 punktów reputacji, aby odpowiedzieć na to pytanie. Wymóg dotyczący reputacji pomaga chronić to pytanie przed spamem i brakiem odpowiedzi.
Nie szukasz odpowiedzi? Przejrzyj inne pytania otagowane java c ++ optymalizacja wydajności gałęzi-przewidywanie lub zadaj własne pytanie.